(1) Technical Field
The present invention relates to a technique for network communications. More specifically, the present invention relates to the use of directional communication nodes that send communication signals in specific directions to minimize interference with those of other nodes.
(2) Discussion
Wireless ad-hoc networks are widely used for setting up networks on the fly in geographic areas that lack, or can not support, traditional of communication infrastructures, e.g. battlefield and disaster relief sites (such as earthquakes and wildfires) that need extensive communication and coordination among wireless terminals. Due to the broadcast nature of omni-directional antennas, multi-user interference constitutes a major hurdle to efficient utilization of the scarce wireless bandwidth. Thus, coordinating the transmissions of independent users such that they can access their next-hop neighbors without destroying each other's signal is the fundamental multiple access problem in wireless ad-hoc networks. Various multiple access protocols have been introduced in the literature assuming omni-directional antennas. Recently, there has been overwhelming evidence that utilizing directional antennas can significantly improve the performance of cellular as well as wireless ad-hoc networks. These potential improvements are made possible by the following attractive features offered by directional antennas:                Interference reduction, made possible by focusing the transmitted power toward the intended neighbor and minimizing it in unintended transmission directions (e.g. directions of unintended neighbors).        Transmission range extension, made possible because focusing transmission power in a specific direction in space increases the reach of the transmitter compared with the case of emitting the same amount of power equally in all directions (e.g. the omni-directional case).        Low probability of detection, made possible because the transmitter is emitting power in a specific direction for a period of time, rather than in all directions all the time.        Low probability of interception, made possible because it is more difficult for an interceptor to jam the transmission of a node using directional antenna.        
In the multiple access problem, there are two fundamental sub-problems that are affected by the use of directional antennas:                Neighbor Discovery: Neighbor discovery schemes are based on broadcast messages from a node to all of its neighbors to either inquire about their identities or to announce its existence via a unique identifier (UID). It is noteworthy that a broadcast message can be delivered to all neighbors via a single omni-directional channel. However, in a case where directional antennas are used, issues arise as to how to efficiently perform neighbor discovery using directional antennas, and how to account for the trade-offs involved in performing neighbor discovery using directional antennas versus omni-directional antennas.        Spatial Reuse (channel reservation): The scenarios shown in FIG. 1 and FIG. 2, discussed in the background above, emphasize the role of directional antennas in improving spatial reuse. In FIG. 1, it may be seen that a pair of transmissions, e.g. those between nodes S and D and between nodes 2 and 10 suffer from interference in the case of omni-directional antennas (shown in FIG. 1). However, this interference can be effectively eliminated via the interference reduction feature of directional antennas, as depicted in FIG. 2. Hence, the potential MAC throughput of an ad-hoc network may be increased using directional antennas.        
Several multiple access techniques (protocols) have been introduced in the literature for wireless ad-hoc networks. A sampling of these is provided in the list of references at the end of this discussion. Most of the references listed describe variations of the CSMA/CA protocol that are modified to cope with the inherent hidden terminal problem. There have been several attempts to introduce multiple access protocols to ad-hoc networks that utilize directional antennas. The work in “Slotted ALOHA multihop packet radio networks with directional antennas” by J. Zander provides a performance analysis study that shows the impact of directional antennas on the performance of slotted ALOHA. On the other hand, the work in “Design algorithms for multi-hop packet radio networks with multiple directional antenna systems” by T-S Yum and K-W Hung introduces a multiple access protocol that minimizes interference by using a group of tones to identify the active neighbors. Other research efforts have attempted to modify the request to send/clear to send (RTS/CTS) handshake mechanism of CSMA/CA protocols to efficiently utilize the interference reduction feature of directional antennas. Still other works have considered specific types of directional antennas, namely “switched beam antennas” that consist of several fixed and predefined beams formed usually with antenna arrays. On the other hand, some works have also considered both switched beam and steerable beam antennas.
In “Medium Access Control Protocols Using Directional Antennas in Ad Hoc Networks” by Y. Ko, V. Shankarkumar and N. Vaidya, the authors assume that each node knows which beam should be used in order to reach a specific neighbor. They also assume that transmissions received by two or more beams on the same node could interfere with each other. They provided two approaches for modifying the CSMA/CA protocol. In the first approach, they considered sending RTS packets in the direction of the destination only (directionally, or D-RTS for short), whereas CTS packets were transmitted in all directions (omni-directionally, or O-CTS for short). There are two major limitations in this protocol. The first, which was indicated by its authors, stems from the fact that D-RTS packets do not reach some neighbors of the source node, which might cause control packet collisions at the source node S (as depicted in FIG. 2), because of attempts to transmit to S or to a neighbor covered by the same beam pointing toward S. To resolve this conflict, the authors proposed a second approach that utilizes both D-RTS and O-RTS (omni-directionally, or O-RTS for short). The authors proposed starting with D-RTS and then switching to O-RTS if collisions arise. However, this solution is inefficient since it does not minimize either the number of control packet collisions caused by neighbors of the source node or the number of nodes that back off unnecessarily. This is primarily due to the tradeoff between using D-RTS packets (which minimize the number of nodes that need to back off) and O-RTS packets (which minimize the number of control packet collisions of the type mentioned previously). The second limitation is due to the fact that sending O-RTS packets to all neighbors, without distinguishing nodes that suffer interference during the directional data transmission, and nodes that do not, could lead to further collisions at a node. Neighbors that lie within the intended direction of data transmission may need to block some, or all, beams from transmission due to the interference they may suffer from the directional data transmission due to multipath fading. On the other hand, neighbors outside of that region need to block only the beam pointing toward the neighbor involved in the transmission. The same argument applies to the O-CTS packets, which do not differentiate between nodes that lie within the direction of acknowledgement (ACK) transmissions and nodes that do not.
In “A MAC Protocol for Mobile Ad Hoc Networks Using Directional Antennas”, by A. Nasipuri, S. Ye, J. You and R. Hiromoto, the authors assume that mobile nodes do not have any location information about their neighbors. Additionally, they employ selection diversity where the receiver uses the signal from the antenna that is receiving the maximum power. They propose to jointly solve the problems of neighbor location discovery and channel reservation. The approach taken is based on sending RTS and CTS packets in all directions, whereas data and acknowledgement packets are sent directionally. The limitation of this approach is that the channel reservation packets, namely the RTS and CTS packets, are sent in all directions, which, in turn, leads to the same problem as is present in plain CSMA/CA; that is, blocking neighbors unnecessarily. The primary reason behind this shortcoming is the authors' attempt to solve the problems of neighbor location discovery and channel reservation simultaneously. While this could have the advantage of reducing the protocol overhead, it could lead to severe degradation in multiple access throughput.
In “CSMA/CA with Beam Forming Antennas in Multi-hop Packet Radio” by M. Sanchez, T. Giles and J. Zander, the authors introduced a number of beam selection policies for CSMA/CA based protocols. First, they proposed the use of omni-directional antennas to send RTS packets (O-RTS), while use directional beams to feedback CTS packets (D-CTS). Based on the previous discussion, it is evident that this protocol suffers the following two drawbacks that significantly affect its throughput: i) using omni-directional RTS packets leads to blocking neighbors unnecessarily; and ii) using D-CTS packets could lead to other neighbors transmitting to the destination, hence causing data packet collisions. The authors also proposed to use D-RTS to resolve the problems of unnecessarily blocking neighbors. Again, this leads to the possibility of neighbors causing control packet collisions at the source node. Although, the proposed protocols achieve performance gains over plain CSMA/CA, they do not guarantee an optimal balance between unnecessary neighbors' back off and collisions tradeoff.
In “Smart Antennas for Future Re-configurable Wireless Communication Networks” by C. Balanis, J. Aberle, J. Capone, T. Duman, S. El-Ghazaly, A. Spanias and T. Thornton, the authors assumed very narrow beam-widths, almost like pencil-beam antenna patterns. Although this assumption may not be practical, the multiple access problem is resolved, from the authors' perspective, via the narrow beam assumption. However, the authors employ the IEEE 802.11 handshake mechanism (RTS/CTS) mainly for location discovery, not for reserving the channel. Thus, this is essentially a neighbor location discovery scheme based on the RTS/CTS handshake packets. However, pencil-beams are generally impractical since beam widths depend on several factors among which are the frequency band and data rate. The authors assert that if the smart antennas are not highly directional, neighboring nodes could cause interference to an ongoing transmission since no channel reservation is made.
Generally, a neighbor is said to be blocked if at least one of its beams is blocked from transmission due to overhearing a channel reservation packet (either RTS or CTS) from neighbor. On the other hand, a neighbor is said to be unblocked if it does not hear any channel reservation packet and, hence, is completely unaware of the ongoing reservation attempt. These unblocked neighbors can initiate a channel reservation request independently and cause interference (collisions) to the ongoing transmission. The set of nodes within the geographic area covered by the transmission radiation pattern of an omni-directional antenna at node x is denoted as a set of neighbors N(x). The set of blocked neighbors of node x is denoted as BN(x), while the set of unblocked neighbors is denoted as UBN(x). This terminology will be used in the case where directional antennas are employed. To begin with however, in review, the scenario shown in FIG. 1 depicts a case where all signals are transmitted omni-directionally (i.e., handshake packets are sent in all directions). This case is referred to as “omni-directional blocking”. In this case, node S wishes to initiate a transmission to node D. Thus, it proceeds by sending an O-RTS (omni-directional request to send) packet and node D responds by an O-CTS (omni-directional clear to send) packet that confirms the reservation to S. For this scenario, it is straightforward to see that the neighbor sets of nodes S and D are given by N(S)={1, 2, 3, 4, 5, 6, D} and N(D)={1, 4, 5, 6, 7, 8, 9, S}, respectively. In this case, the set of blocked neighbors includes all neighbors and the set of unblocked neighbors is empty, i.e. BN(S)=N(S); UBN(S)={ }; BN(D)=N(D); and UBN(D)={ }. This is due to the fact that the reservation packets are sent in all directions and hence all neighbors become aware of the ongoing transmission and refrain from transmission. This scheme is only favorable if a neighbor's transmission causes interference to the ongoing transmission (e.g. node 5 transmitting to node 6 causes collision at D). However, if the neighbor wishes to transmit data, in a directional manner, to another node such that it will not cause interference to the ongoing transmission (e.g., node 2 sending to node 10, or node 8 sending to node 11), it will be blocked unnecessarily. This, in turn, degrades the multiple access throughput and illustrates the drawbacks of plain CSMA/CA protocols due to the fact that they do not utilize the interference reduction feature of directional antennas to the full extent. This is referred to herein as the “unnecessary blocking” problem.
To resolve the “unnecessary blocking” problem caused by omni-directional reservations, several directional reservation schemes have been introduced in the literature, some of which were previously mentioned. The scenario depicted in FIG. 2, shows a node setting similar to that of FIG. 1. To gain more insight about the design tradeoffs, FIG. 2 presents the other extreme, where handshake packets are sent strictly in a directional manner (D-RTS/D-CTS). This case is referred herein to as “directional blocking”. Assume a transmission scenario similar to the one considered earlier where node S wishes to initiate a transmission to node D. Thus, it sends a D-RTS and node D responds by sending a D-CTS that confirms the reservation to S. In this case, it is straightforward to notice that BN(S)={4, 5,6, D}; UBN(S)={1, 2, 3}; BN(D)={4, 5, S}; and UBN(D)={1, 6, 7, 8, 9}. Unlike the case of omni-directional reservation depicted in FIG. 1, neighbors are partitioned between the two groups due to the fact that the reservation packets are sent directionally, and hence some neighbors are aware of the ongoing transmission while others are not. Clearly, there is a tradeoff, between the possibility of collisions caused by unblocked neighbors and the number of unnecessarily blocked neighbors, associated with the directional reservation approach. Thus, a neighbor knowing about an ongoing transmission may degrade performance, because of unnecessary blocking (e.g. node 2 sending to node 10, or node 8 sending to 11), while another neighbor not knowing about an ongoing transmission could degrade performance as well, because of the possibility of collisions (e.g. node 2 sending to node S, or node 6 sending to D). This tradeoff cannot be solved by either of the aforementioned two extremes.
To this end, it is important to note that the two handshaking extremes, namely omni-directional handshaking and directional handshaking, are inefficient. This is due to the fact that omni-directional handshaking can lead to unnecessary blocking of neighboring nodes that wish to transmit in a different direction. On the other hand, directional handshaking solves the problem of blocking neighbors unnecessarily. However, it can lead to the case where some neighbors are left unaware of the ongoing transmission, and can lead to packet collisions.
Because of the shortcomings present in the state of the art, a need exists for a technique for overcoming the limitations inherent in both strictly omni-directional and strictly directional handshaking routines.